#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<ctime>
#include<string.h>
#include<math.h>
#include<list>
 
using namespace std;
 
#define ll long long
#define pii pair<int,int>
const int inf = 1e9 + 7;
 
char to[27];
bool vis[27];
vector<pii>loop;//fist 循环节长度为first 有second个循环节长度为first
 
void calLoop(){
    for(int i=0;i<26;++i){
        to[i]-='a';
    }
    map<int,int>mp;
    fill(vis,vis+27,0);
    loop.clear();
    for(int i=0;i<26;++i){
        if(vis[i]==0){
            vis[i]=1;
            int ans=1;
            int x=to[i];
            while(x!=i){
                vis[x]=1;
                ++ans;
                x=to[x];
            }
            mp[ans]+=1;
        }
    }
    for(auto it=mp.begin();it!=mp.end();++it){
        loop.push_back(*it);
    }
}
 
ll lcm(ll a,ll b){
    ll tmp=__gcd(a,b);
    return a/tmp*b;
}
 
ll quickMulti(ll a,ll n){
    ll ans=1;
    ll t=a%inf;
    while(n){
        if(n&1){
            ans=(ans*t)%inf;
        }
        t=(t*t)%inf;
        n>>=1;
    }
    return ans;
}
 
inline ll mod(ll x){
    return (x%inf+inf)%inf;
}
 
ll f(vector<int>&vec,int n){//容斥
    ll ans=0;
    int nv=vec.size();
    for(int i=1,end=1<<nv;i<end;++i){
        ll flag=-1;
        int sum=0,num=0;
        for(int j=0;j<nv;++j){
            if((1<<j)&i){
                sum+=vec[j];
                ++num;
            }
        }
        if(num%2==nv%2){
            flag=1;
        }
        ll t=quickMulti(sum,n);
        ans=(ans+mod(flag*t))%inf;
    }
    return ans;
}
 
ll slove(int n){
    calLoop();
    ll ans=0;
    vector<int>vec;//当前选择了的循环节包含的字母数
    for(int i=1,end=1<<loop.size();i<end;++i){//枚举循环节的状态
        ll ans1=1;//选择了这几个循环节的贡献
        vec.clear();
        for(int j=0;j<loop.size();++j){
            if((1<<j)&i){
                ans1=lcm(ans1,loop[j].first);
                vec.push_back(loop[j].first*loop[j].second);
            }
        }
        if(vec.size()>n){
            continue;
        }
        ll ans2=f(vec,n);
        ans=(ans+ans1*ans2)%inf;
    }
    return ans;
}
 
int main()
{
//freopen("in.txt","r",stdin);
    //freopen("/home/lu/Documents/w.txt","w",stdout);
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d%s",&n,to);
        printf("%lld\n",slove(n));
    }
    return 0;
}